package com.wpp.algorithm.lagou.part1.lesson4;

import com.wpp.data_structure.queue.DefaultQueue;
import com.wpp.data_structure.queue.MyQueue;

/**
 * @author wpp25
 * @date 2021/6/3 20:44
 * @description：
 *   学习目标
 *   - 了解算法题的解题思路
 *   - 数组 + 双指针
 *   - 队列的特点
 *
 *
 */
public class Lesson4 {

    private static int[] array = new int[10000];



    /**
     * 题目：
     *  最近的请求次数： 在 RecentCounter 类中有个方法 ： ping(int t) , t 代表某个时间（毫秒） ，
     *  返回从3000ms前 （时间范围：[t-3000,t]） 到现在ping 数
     *  eg: inputs {1,100,3001,3002}
     *     outputs [1,2,3,3]
     */

    public static void main(String[] args) {
        int[] arr = {1,100,3001,3002,6001,6002,9003};
        for (int i : arr) {
            System.out.printf("%s ",sampleAnswer(i));
        }
        System.out.println();
        for (int i : arr) {
            System.out.printf("%s ",betterAnswer(i));
        }
        System.out.println();
        for (int i : arr) {
            System.out.printf("%s ",answerByQueue(i));
        }
    }

    // 暴力解法
    private static int sampleAnswer(int t) {
        int end = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == 0) {
                array[i] = t;
                end = i;
                break;
            }
        }
        int count = 0;
        while (array[end--] >= t - 3000){
            count++;
            if (end < 0) {
                break;
            }
        }
        return count;
    }


    private static int start = 0;
    private static int end = 0;
    private static int[] arr1 = new int[3002];
    /**
     * 双指针解法
     *
     * 索引 start 到 end 之间的时间 就是 3000ms内ping的数（包括 start 和 end的ping）
     * 细节 end++
     * @param t
     * @return
     */
    private static  int betterAnswer(int t) {
        arr1[end++] = t;
        end = end == arr1.length ? 0 : end;

        while (arr1[start] < t - 3000) {
            start++;
            if (start == arr1.length) {
                start = 0;
            }
        }

        if (start > end) {
            return arr1.length - (start - end);
        }

        return end - start;
    }

    private static MyQueue<Integer> queue = new DefaultQueue<>();

    private static int answerByQueue(int t) {
        queue.add(t);

        while (queue.tail() - queue.top() > 3000) {
            queue.poll();
        }

        return queue.getSize();
    }
}
